#include<cstdio>//uncle-lu
#include<cstring>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}	

int Map[110][110];
int F[110][110];//到达x,y的最优值.
int x_turn[4]={1, -1, 0, 0};
int y_turn[4]={0, 0, 1, -1};
int n, m, Ans;

void DFS(int x, int y, bool flag, int sum)//站在x, y flag是否上一个位置用魔法了。
{
	if(F[x][y] <= sum)return ;//最优化剪枝，记忆化搜索.
	F[x][y] = sum;

	if(x == n && y == n)//搜索到头了
	{
		Ans = std::min(sum, Ans);
		return ;
	}

	for (int i = 0; i <= 3; i++) //枚举4个方向
	{
		int xx = x + x_turn[i], yy = y + y_turn[i];
		if( xx < 1 || xx > n || yy < 1 || yy > n )continue;

		if( Map[xx][yy] == -1 )
		{
			if(flag)continue;//之前是否使用过魔法.
			Map[xx][yy] = Map[x][y];
			DFS(xx, yy, true, sum+2);
			Map[xx][yy] = -1;
		}
		else
		{
			if(Map[xx][yy] == Map[x][y])
				DFS(xx, yy, false, sum);
			else
				DFS(xx, yy, false, sum+1);
		}
	}
	return ;
}

int main()
{
	memset(Map, -1, sizeof(Map));
	memset(F, 0x7f7f7f, sizeof(F));
	Ans = 0x7f7f7f7f;
	read(n);read(m);
	int x, y, c;
	for (int i = 1; i <= m; i++) 
	{
		read(x);read(y);read(c);
		Map[x][y] = c;
	}

	DFS(1,1,false,0);

	if(Ans == 0x7f7f7f7f)
		printf("-1");
	else
		printf("%d", Ans);

	return 0;
}
